package 回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. 组合总和
 *给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 *
 *
 * 解题思路
 * 组合总和问题需要找到所有和为给定目标值的候选元素组合，允许重复使用同一元素，但要求组合不重复。通过回溯算法实现，关键点在于控制递归遍历的起点和剪枝优化：
 *
 * 排序数组：预处理数组，方便后续剪枝。
 * 回溯框架：
 * 终止条件：当剩余目标值为0时，保存当前路径。
 * 循环选择元素：从当前起点开始遍历候选元素。
 * 剪枝：若当前元素超过剩余目标值，提前终止后续循环。
 * 避免重复组合：通过固定遍历顺序（每次从当前起点开始），保证组合中的元素非递减，避免重复。
 */
public class L_39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 排序数组，方便后续剪枝
        backtrack(res,new ArrayList<>(),candidates,target,0);
        return res;
    }

    private void backtrack(List<List<Integer>> res,List<Integer> path,int[] candidates,int remain,int start){
        // 递归终止条件，找到一个满足条件的组合后返回
        if (remain == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        // 循环遍历选择元素
        for (int i = start; i < candidates.length; i++) {
            // 剪枝优化，当前元素大于剩余目标值，提前终止后续循环
            if (candidates[i] > remain){
                return;
            }
            path.add(candidates[i]);
            // 继续递归，添加当前元素到路径中
            backtrack(res,path,candidates,remain - candidates[i],i);
            // 回溯，撤销选择，从路径中移除当前元素
            path.remove(path.size() - 1);
        }
    }
}
